class Solution
{
public:
    long long minimumTime(vector<int>& time, int totalTrips)
    {
        // 本题求这个最小花费时间是有一个单调性的
        // 假设只有那辆跑一趟耗时最长的公交车，那么完成totalTrips趟就是需要time[i] * totalTrips
        // 假设有另一辆来分担了，那么这个花费时间就会减小
        // 所以存在一个最小时间，从这个最小时间往后都是能完成totalTrips趟的
        // 找到那辆跑一趟耗时最长的公交车

        auto check = [&](long long curTime)->bool
        {
            long long sum = 0;
            for(int &x : time)
            {
                sum += curTime / x;
                if(sum >= totalTrips)
                    return true;
            }
            return false;
        };

        long long mx = *max_element(time.begin(), time.end());
        long long left = 1;   // 题目保证最少一趟
        long long right = (long long)mx * totalTrips;

        while(left < right)
        {
            long long mid = (right + left) / 2;
            if(check(mid))
                right = mid;
            else
                left = mid + 1;     // 不能完成还需要往上累加时间
        }
        return left;
        // 时间复杂度：O(N*Log(Max(Time[i])∗Totaltrips))
    }
};